//
//  IsValid.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/8/14.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  20. 有效的括号

import UIKit

/*
 20. 有效的括号
 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

 有效字符串需满足：

 左括号必须用相同类型的右括号闭合。
 左括号必须以正确的顺序闭合。
 注意空字符串可被认为是有效字符串。

 示例 1:

 输入: "()"
 输出: true
 示例 2:

 输入: "()[]{}"
 输出: true
 示例 3:

 输入: "(]"
 输出: false
 示例 4:

 输入: "([)]"
 输出: false
 示例 5:

 输入: "{[]}"
 输出: true
 */

class IsValid: NSObject {
    
    //用栈来解决这个问题     12ms
    func isValid(_ s: String) -> Bool {
        if s.count == 0 {
            return true
        }
        if s.count == 1{
            return false
        }
        
        var stack = [String]()
        
        let stringArr = Array(s)
        
        for str in stringArr{
            if str == "(" || str == "[" || str == "{"{
                stack.append(String(str))
            }else{
                if str == ")"{
                    if stack.last == "("{
                        stack.removeLast()
                    }else{
                        return false
                    }
                }else if str == "]"{
                    if stack.last == "[" {
                        stack.removeLast()
                    }else{
                        return false
                    }
                }else if str == "}"{
                    if stack.last == "{"{
                        stack.removeLast()
                    }else{
                        return false
                    }
                }
            }
        }
        return stack.isEmpty
    }
    
    //优化    8ms
    func isValid2(_ s: String) -> Bool {
        if s.count == 0 {
            return true
        }
        if s.count%2 != 0{
            return false
        }
        
        let hashTab = [")":"(",
                       "]":"[",
                       "}":"{"]
        
        var stack = [String]()
        
        let stringArr = Array(s)
        
        for str in stringArr{
            if hashTab.values.contains(String(str)){
                stack.append(String(str))
            }else if hashTab[String(str)] != stack.popLast(){
                return false
            }
        }
        
        return stack.isEmpty
    }
}
